課程資訊
課程名稱
 自動機與形式語言
Formal Languages and Automata Theory 
開課學期
 112-1 
授課對象
 資訊工程學系  
授課教師
 林忠緯 
課號
 CSIE3110 
課程識別碼
 902E43500 
班次
 02 
學分
 3.0 
全/半年
 半年 
必/選修
 必帶 
上課時間
 星期一3,4,5(10:20~13:10) 
上課地點
 資103 
備註
 本課程以英語授課。
限本系所學生(含輔系、雙修生) 且 限學士班三年級以上 且 限學號雙號
總人數上限：100人 
  
課程簡介影片
 
核心能力關聯
 核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

This course covers the basics of theory of computation. The material includes regular languages, context-free languages, models of computation, decidability, reducibility, and complexity. Formal and rigorous mathematical proof is one of the emphases of this course. 

課程目標
 Students are expected to have basic knowledge of theory of computation. 
課程要求
 Students should be familiar with mathematical proof. 
預期每週課後學習時數
  
Office Hours
  
指定閱讀
  
參考書目
  
評量方式
(僅供參考)
  
No.
項目
百分比
說明
1. 
 Midterm 1 
30% 
 Week 5 
2. 
 Midterm 2 
30% 
 Week 11 
3. 
 Final Exam 
40% 
 Week 16 
4. 
 Homework 
0% 
  
 
課程進度
週次
日期
單元主題
第1週
 9/4  Introduction 
第2週
 9/11  Finite Automata 
第3週
 9/18  Regular Expressions 
第4週
 9/25  Context Free Grammars 
第5週
 10/2  Midterm 1 
第6週
 10/9  Holiday 
第7週
 10/16  Pushdown Automata 
第8週
 10/23  Turing Machines 
第9週
 10/30  Variants of Turing Machines 
第10週
 11/6  Definition of Algorithm 
第11週
 11/13  Midterm 2 
第12週
 11/20  Decidability 
第13週
 11/27  Reducibility 
第14週
 12/4  Complexity Theory 
第15週
 12/11  TBD (Buffer Week) 
第16週
 12/18  Final Exam 
第17週
 12/25  TBD (Additional Office Hours) 
第18週
 1/1  TBD (Additional Office Hours)